#include "LinkStack.h"
#include"LinkQueue.h"

// size_t partition(int *array,size_t start, size_t end)
// {
//     size_t left = start;
//     size_t right = end;
//     int temp = array[start];
//     while(left < right)
//     {
//         while(array[right] > temp && left < right)
//             right--;
//         if(left < right)
//             array[left++] = array[right];
//         while(array[left] < temp && left < right)
//             left++;
//         if(left < right)
//             array[right--] = array[left];
//     }
//     array[left] = temp;
//     return left;
// }
// //借助栈实现非递归的快速排序
// void FastNoRecur(int *a,size_t start,size_t end)
// {
//     LinkStack s;//存放区间的栈
//     s.Push((void*)start);
//     s.Push((void*)end);


//     while(s.IsEmpty() == false)//栈不为空
//     {
//         //取区间
//         size_t right = (size_t)*s.GetTop();
//         s.Pop();
//         size_t left = (size_t)*s.GetTop();
//         s.Pop();
//         size_t mid = partition(a,left,right);//把区间传给分组排序
//         if(mid != 0 && left < mid - 1)
//         {
//             //左区间入栈
//             s.Push((void*)left);
//             s.Push((void*)(mid-1));
//         }
//         if( right > mid + 1)
//         {
//             //右区间入栈
//             s.Push((void*)(mid + 1));
//             s.Push((void*)right);

//         }
   
//     }


// }

size_t partition(int *a,size_t start,size_t end)
{
    size_t left = start;
    size_t right = end;
    int temp = a[start];
    while(left < right)
    {
        while(a[right] > temp && left < right)
            right--;
        if(left < right)
            a[left++] = a[right];
        while(a[left] < temp && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];
    }
    a[left] = temp;
    return left;
}


void FastNoRecur(int *a,size_t start,size_t end)
{
    LinkStack s;
    s.Push((void*)start);
    s.Push((void*)end);

    while(s.IsEmpty() == false)
    {
        size_t right =(size_t)*s.GetTop();
        s.Pop();
        size_t left = (size_t)*s.GetTop();
        s.Pop();
        size_t mid = partition(a,left,right);
        if(mid != 0 && left < mid - 1)
        {
            s.Push((void*)left);
            s.Push((void*)(mid - 1));
        }
        if(right > mid + 1)
        {
            s.Push((void*)(mid + 1));
            s.Push((void*)right);
        }
    }
}

int main()
{
    // LinkStack s;
    // for(long i = 0;i < 20;i++)
    // {
    //     s.Push((void*)(i+1));
    // }
    // while(s.IsEmpty() == false)
    // {
    //     std::cout<<*(int*)s.GetTop()<<" ";
    //     s.Pop();
    // }
    int a[] = {4,1,5,2,7,3,9};
    FastNoRecur(a,0,sizeof(a)/sizeof(a[0]) - 1);
    for(int i = 0;i < sizeof(a)/sizeof(a[0]);i++)
        std::cout<<a[i]<<" ";
    std::cout<<std::endl;


    // LinkQueue q;
    // for(long i = 0;i < 20;i++)
    //     q.Push((void*)(i + 1));
    // while(q.IsEmpty() == false)
    // {
    //     std::cout<<(long)*q.GetFront()<<" ";
    //     q.Pop();
    // }
    // std::cout<<std::endl;

    // q.Push(1);
    // while(q.IsEmpty() == false)
    // {
    //     std::cout<<(long)*q.GetFront()<<" ";
    //     q.Pop();
    // }
    // std::cout<<std::endl;
    return 0;
}